Consulta de Guías Docentes



Academic Year/course: 2022/23

439 - Bachelor's Degree in Informatics Engineering

30229 - Basic Algorithms


Syllabus Information

Academic Year:
2022/23
Subject:
30229 - Basic Algorithms
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
Degree:
439 - Bachelor's Degree in Informatics Engineering
ECTS:
6.0
Year:
3
Semester:
Second semester
Subject Type:
---
Module:
---

1. General information

1.1. Aims of the course

In this course the student will improve his/her ability to design and implement algorithms by identifying and applying techniques that can be used to obtain efficient solutions for a wide range of problems. Some basic techniques willl be presented, such as: divide and conquer, greedy algorithms, dynamic programming, backtracking, branch and bound, etc.

The student will learn how to recognize problems that require these type of techniques to be solved and how to apply them.

These objectives are aligned with some of the Sustainable Development Goals, SDG, of the Agenda 2030 (https://www.un.org/sustainabledevelopment/en/) and certain specific targets, in such a way that the acquisition of the learning outcomes of the course provides training and competence to the student to contribute in certain measure to their achievement:

  • Goal 8: Promote inclusive and sustainable economic growth, employment and decent work for all.
    Target 8.5: By 2030, achieve full and productive employment and decent work for all women and men, including for young people and persons with disabilities, and equal pay for work of equal value
  • Goal 9: Build resilient infrastructure, promote sustainable industrialization and foster innovation.
    Target 9.1: Develop quality, reliable, sustainable and resilient infrastructure, including regional and transborder infrastructure, to support economic development and human well-being, with a focus on affordable and equitable access for all.

1.2. Context and importance of this course in the degree

The Computing Mention covers a wide range of concepts, from theoretical and algorithmic foundations to the forefront of the development in bioinformatics, robotics, computer vision, computer games and other interesting areas.

Basic Algorithms is the first course of the Computing Mention and it focuses on the design of correct and efficient algorithms by means of knowledge and application of a set of basic techniques.

1.3. Recommendations to take this course

Interest and effort, in addition to the knowledge acquired in the previous courses of mathematics, programming, data structures and algorithms, and theory of computation.

2. Learning goals

2.1. Competences

Combine general and specific engineering knowledge to generate innovative and competitive proposals in the professional activity.

Solve problems and make decisions with initiative, creativity, and critical thinking.

Communicate and transmit knowledge, abilities and skills in Spanish and English.

Evaluate the computational complexity of a problem, know algorithmic strategies that can lead to its resolution, recommend and develop those that guarantees the best performance according the requirements.

2.2. Learning goals

To pass this course, the student will have to demonstrate the following results:

He/she knows several solution techniques and problems that use them.

He/she knows how to accommodate a general solution technique to solve concrete problems.

He/she knows how to identify the most relevant components of a problem and select the most appropriate solution technique to solve it, in addition to arguing in a reasoned manner such selection.

He/she knows how to compare problems and use such comparison to solve one problem from an efficient solution of another problem.

He/she can reason about the correctness and efficiency of the used algorithms.

He/she is able to work in a team, identify the goals of the team, define a work plan to achieve them, recognize the different roles within a team and assume the commitment of the assigned tasks.

He/she is able to self-learn and to manage project development, including organization and management time.

He/she appreciate the need for continuous learning.

2.3. Importance of learning goals

Given a problem, there is a wide range of algorithms available to solve it and it is important to decide which of them to use. Depending on the requirements, we may need to select the algorithm that takes the least time or use the least space or is the easiest to implement and so on. It is also possible that none of the available algorithms is fully adequate to solve the problem and we need to design a new one.

The study of algorithms allows us to evaluate the effect of problem features on the available algorithms in order to select the algorithm that guarantees the requirements fulfillment and, also, to design a new algorithm to solve a concrete problem.

3. Assessment (1st and 2nd call)

3.1. Assessment tasks (description of tasks, marking system and assessment criteria)

The student will have to demonstrate that he/she achieved the expected learning goals through the following evaluation activities:

Practical programming tasks to be carried out in teamwork: the size of the workteams will be set at the beginning of the course. The task results presented by the students will be graded with a value from 0 to 10. The evaluation criteria include the correctness of the implementation according to the requirements, the design quality, the adequate application of the solution techniques, the time spent as well as the ability of the workteam members to explain and justify the design choices.

Global assessment

  1. Practical programming tasks (teamwork): 45%
  2. Exam: 55%

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

The learning process that is designed for this subject is based on the following:

  • The study and work continued since the first day of class.
  • Learning concepts and methodologies for the design and implementation of correct and efficient algorithms through lectures, in which student participation is encouraged.
  • The application of such knowledge to the design and analysis of algorithms and programs in the classes of problems. In these classes, students will play an active role in the discussion and resolution of problems.
  • Teamwork to address the practical programming tasks; the results will be reflected in the delivery of suitably designed and documented programs, as well as the explanation and justification of design and decisions adopted.
  • Continued work combining the understanding of concepts, analysis and problem solving using "pencil and paper", and the set-up of computer programming projects.

4.2. Learning tasks

The course includes the following learning tasks: 

In some classes, the previously presented concepts and techniques will be used to solve problems.

The practical programming tasks will be carried out in a computer lab or using personal computers of students at home. In these sessions, students will work in teams and perform a number of programming tasks directly related to the topics studied in the course. The programming tasks will be delivered within the fixed deadlines.

The progress of the student assignments will be supervised by a professor in tutorials.

4.3. Syllabus

The course will address the following topics: 

  1. Introduction.
  2. Divide and conquer.
  3. Greedy algorithms.
  4. Dynamic programming.
  5. Backtracking.
  6. Branch and bound.
  7. Linear programming and reductions.

4.4. Course planning and calendar

Scheduled sessions and presentation of works.

The organization of the subject is as follows.

  • Theoretical classes (2 hours per week)
  • Problems classes (1 hour weekly)
  • Lab. sessions (2 hours per week)

Presentation of practical programming tasks:

Practical programming tasks should be carried out and presented as specified for each of them, and within fixed deadlines.

Student Work.

The dedication of the student to achieve the learning outcomes in this course is estimated at 150 hours distributed as follows:

  • 60 hours, approximately, of classroom activities (theoretical and problem solving classes) and lab. activities;
  • 84 hours of effective personal study;
  • 6 hours, approximately, of evaluation activities.

4.5. Bibliography and recommended resources

https://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=30229


Curso Académico: 2022/23

439 - Graduado en Ingeniería Informática

30229 - Algoritmia básica


Información del Plan Docente

Año académico:
2022/23
Asignatura:
30229 - Algoritmia básica
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
Titulación:
439 - Graduado en Ingeniería Informática
Créditos:
6.0
Curso:
3
Periodo de impartición:
Segundo semestre
Clase de asignatura:
---
Materia:
---

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

En esta asignatura el alumno mejorará su capacidad para diseñar y desarrollar algoritmos haciendo énfasis en la identificación y aplicación de los esquemas que puedan ser utilizables para obtener soluciones eficientes a una amplia gama de problemas. Se presentarán algunos de los esquemas algorítmicos fundamentales, como: dividir para vencer, voracidad, programación dinámica, búsqueda con retroceso, ramificación y poda, etc. El alumno aprenderá a reconocer los problemas que requieren este tipo de esquemas para su resolución y cómo aplicarlos.

Estos planteamientos y objetivos están alineados con algunos de los Objetivos de Desarrollo Sostenible, ODS, de la Agenda 2030 (https://www.un.org/sustainabledevelopment/es/) y determinadas metas concretas, de tal manera que la adquisición de los resultados de aprendizaje de la asignatura proporciona capacitación y competencia al estudiante para contribuir en cierta medida a su logro:

  • Objetivo 8: Promover el crecimiento económico sostenido, inclusivo y sostenible, el empleo pleno y productivo y el trabajo decente para todos.
    Meta 8.4. Mejorar progresivamente, de aquí a 2030, la producción y el consumo eficientes de los recursos mundiales y procurar desvincular el crecimiento económico de la degradación del medio ambiente, conforme al Marco Decenal de Programas sobre modalidades de Consumo y Producción Sostenibles, empezando por los países desarrollados.
  • Objetivo 9: Construir infraestructuras resilientes, promover la industrialización inclusiva y sostenible y fomentar la innovación.
    Meta 9.1. De aquí a 2030, desarrollar infraestructuras fiables, sostenibles, resilientes y de calidad, incluidas infraestructuras regionales y transfronterizas, para apoyar el desarrollo económico y el bienestar humano, haciendo especial hincapié en el acceso asequible y equitativo para todos.

1.2. Contexto y sentido de la asignatura en la titulación

La Especialidad en Computación abarca una amplia gama de conceptos, desde los fundamentos teóricos y algorítmicos hasta la vanguardia de los desarrollos en bioinformática, robótica, visión por computador, videojuegos, y otras áreas interesantes. Algoritmia básica es la primera de las asignaturas de la Especialidad y se centra en el diseño de algoritmos correctos y eficientes mediante el conocimiento y aplicación de un conjunto de esquemas reutilizables.

1.3. Recomendaciones para cursar la asignatura

Interés y esfuerzo, además de los conocimientos adquiridos en las asignaturas previas de matemáticas, programación, estructuras de datos y algoritmos y teoría de la computación.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para...

Combinar los conocimientos generalistas y los especializados de Ingeniería para generar propuestas innovadoras y competitivas en la actividad profesional.

Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.

Comunicar y transmitir conocimientos, habilidades y destrezas en castellano y en inglés.

Evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

Conoce esquemas algorítmicos variados y problemas fundamentales que utilizan los mismos.

Sabe particularizar esquemas algorítmicos generales para resolver problemas.

Sabe identificar las componentes más relevantes de un problema y seleccionar la técnica algorítmica más adecuada para el mismo, además de argumentar de forma razonada dicha elección.

Sabe comparar problemas y utilizar dicha comparación para resolver un problema a partir de una solución eficiente de otro.

Sabe razonar sobre la corrección y eficiencia de los algoritmos avanzados que se utilizan.

Habilidad para trabajar en grupo, identificar objetivos del grupo, trazar un plan de trabajo para alcanzarlo, reconocer los diferentes papeles dentro de un equipo y asume el compromiso de las tareas encomendadas.

Gestión del autoaprendizaje y de desarrollo incluyendo el tiempo de gestión y de organización.

Apreciar la necesidad del aprendizaje continuo.

2.3. Importancia de los resultados de aprendizaje

La Algoritmia se define como el estudio de los algoritmos. Cuando nos disponemos a resolver un problema, es posible que haya toda una gama de algoritmos disponibles. En este caso, es importante decidir cuál de ellos hay que utilizar. Dependiendo de nuestras prioridades y de los límites del equipo que esté disponible para nosotros, quizá necesitemos seleccionar el algoritmo que requiera menos tiempo, o el que utilice menos espacio, o el que sea más fácil de programar y así sucesivamente. La respuesta puede depender de muchos factores, tales como los números implicados, la forma en que se presenta el problema, o la velocidad y capacidad de almacenamiento del equipo de computación disponible. Quizás suceda que ninguno de los algoritmos disponibles sea totalmente adecuado, así que tendremos que diseñar un algoritmo nuevo por nuestros propios medios. La Algoritmia es la ciencia que nos permite evaluar el efecto de estos diferentes factores externos sobre los algoritmos disponibles, de tal modo que sea posible seleccionar el que más se ajuste a nuestras circunstancias particulares; también es la ciencia que nos indica la forma de diseñar un nuevo algoritmo para una tarea concreta.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluación

Se plantearán enunciados prácticos de programación. Para ello se formarán equipos integrados por un número determinado de alumnos que se fijará al principio del curso. Los trabajos presentados por los alumnos se calificarán con una nota cuantitativa de 0 a 10. Para obtener dichas notas se valorará el funcionamiento de los programas según especificaciones, la calidad de su diseño y su presentación, la adecuada aplicación de los métodos de resolución, el tiempo empleado, así como la capacidad de cada uno de los integrantes del equipo para explicar y justificar el diseño realizado.

Evaluación global

La prueba global de evaluación de la asignatura consta de dos partes:

  • Parte práctica. Presentación de trabajos prácticos de programación en los que se obtendrá una calificación de prácticas que ponderará un 45% de la nota final de la asignatura.
  • Examen escrito en el que se deberán resolver problemas de naturaleza similar a los planteados en clase. La calificación obtenida pondera un 55% de la nota final de la asignatura.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

El estudio y trabajo continuado desde el primer día de clase.

El aprendizaje de conceptos y metodologías para el diseño e implementación de algoritmos correctos y eficientes a través de las clases magistrales, en las que se favorecerá la participación de los alumnos.

La aplicación de tales conocimientos al diseño y análisis de algoritmos y programas en las clases de problemas. En estas clases los alumnos desempeñarán un papel activo en la discusión y resolución de los problemas.

El trabajo en equipo desarrollado para resolver las prácticas de la asignatura, equipos integrados como máximo por dos alumnos, y cuyo resultado se plasma en la entrega de programas resultantes convenientemente diseñados y documentados, así como en la explicación y justificación del diseño realizado y decisiones adoptadas.

Un trabajo continuado en el que se conjugue la comprensión de conceptos, el análisis y la resolución de problemas de programación utilizando "lápiz y papel" y la puesta a punto en computador de algunos proyectos de programación.

4.2. Actividades de aprendizaje

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

En las clases impartidas en el aula se desarrollará el temario de la asignatura.

En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura. Se propondrán problemas y ejercicios para ser resueltos antes de la clase de problemas en la que se presentarán y discutirán diferentes soluciones a dichos problemas. También se propondrán ejercicios durante la sesión de problemas para ser resueltos durante la misma, algunos de forma individual y otros para ser trabajados en grupo.

El trabajo de prácticas se desarrolla en un laboratorio informático o bien en los computadores personales de los alumnos, en casa. En estas sesiones los alumnos deberán trabajar en equipo y realizar una serie de trabajos de programación directamente relacionados con los temas estudiados en la asignatura. Para ello se propondrán una serie de trabajos o ejercicios de programación para que los alumnos los resuelvan en grupo y los entreguen dentro de los plazos de tiempo que se fijen en cada caso.

La supervisión de los trabajos se concreta en tutorías dedicadas a controlar la realización de los trabajos y resolver dudas que surjan al alumnado.

4.3. Programa

  1. Introducción.
  2. Divide y vencerás.
  3. Algoritmos voraces.
  4. Programación dinámica.
  5. Búsqueda con retroceso.
  6. Ramificación y poda.
  7. Programación lineal y reducciones.

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Calendario de sesiones y presentación de trabajos

La organización docente de la asignatura prevista es la siguiente.

  • Clases teóricas (2 horas semanales)
  • Clases de problemas (1 hora semanal)
  • Prácticas (2 horas semanales)

Presentación de trabajos prácticos:

Los trabajos prácticos deberán ser realizados y presentados de acuerdo a lo especificado para cada uno de ellos, y dentro de las fechas límite que se anunciarán en el enunciado de cada uno de los trabajos propuestos o con suficiente antelación.

 

Trabajo del estudiante

La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 150 horas distribuidas del siguiente modo:

  • 60 horas, aproximadamente, de actividades con el/la profesor/a (clases teóricas, de problemas y prácticas en laboratorio);
  • 84 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación de clases, desarrollo de programas);
  • 6 horas, aproximadamente, de pruebas de evaluación.

El calendario de exámenes y las fechas de entrega de trabajos se anunciarán con suficiente antelación en la página web de la asignatura.

4.5. Bibliografía y recursos recomendados

https://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=30229